翻訳と辞書
Words near each other
・ Enter Batgirl, Exit Penguin
・ Enter by the Twelfth Gate
・ Entamoeba histolytica
・ Entamoeba invadens
・ Entamoeba moshkovskii
・ Entamoeba polecki
・ Entamoebidae
・ Entandrophragma
・ Entandrophragma caudatum
・ Entanet
・ Entangled
・ Entangled (Partington)
・ Entangled (Red Dwarf)
・ Entangled (song)
・ Entanglement
Entanglement (graph measure)
・ Entanglement distillation
・ Entanglement witness
・ Entanglement-assisted classical capacity
・ Entanglement-assisted stabilizer formalism
・ Entanglements (Parenthetical Girls album)
・ Entarisi ala benziyor
・ Entartistes
・ Entasaf Al-Layl
・ Entasekera
・ Entasi
・ Entasis
・ Entasis (company)
・ Entatic state
・ Entdecker


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Entanglement (graph measure) : ウィキペディア英語版
Entanglement (graph measure)
In graph theory, entanglement of a directed graph is a number measuring how strongly
the cycles of the graph are intertwined. It is defined in terms of a mathematical game in which
''n'' cops try to capture a robber, who escapes along the edges of the graph. Similar to other
graph measures, such as cycle rank, some algorithmic problems, e.g. parity game, can be
efficiently solved on graphs of bounded entanglement.
== Definition ==

The entanglement game〔D. Berwanger and E. Grädel,
(Entangelement – A Measure for the Complexity of Directed Graphs with Applications to Logic and Games ),
Proceedings of LPAR'04, vol. 3452 of LNCS, pp. 209–223 (2004)〕 is played by ''n'' cops against a robber on
a directed graph ''G''. Initially, all cops are outside the graph and the robber selects an arbitrary starting vertex
''v'' of ''G''. Further on, the players move in turn. In each move the cops either stay where they are, or place one
of them on the vertex currently occupied by the robber. The robber must move from her current vertex, along an edge,
to a successor that is not occupied by a cop. The robber must move if no cop is following him. If there is
no free successor to which the robber can move, she is caught, and the cops win. The robber wins if she
cannot be caught, i.e. if the play can be made to last forever.
A graph ''G'' has entanglement ''n'' if ''n'' cops win in the entanglement game on ''G'' but ''n'' − 1 cops lose the game.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Entanglement (graph measure)」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.